1. Field of the Invention
More particularly, the present invention is related to scheduling requests in a solid state memory device.
2. Description of the Related Art
Solid state memory devices encompass rewritable non-volatile memory devices which can use electronic circuitry for storing data. Currently, solid state memory devices replace conventional storage devices such as hard disk drives and optical disk drives in some arenas, such as in mass storage applications for laptops or desktops. Solid state memory devices are also investigated for replacing conventional storage devices in other areas such as in enterprise storage systems. This is because solid state memory devices offer exceptional bandwidth as well as excellent random I/O (input/output) performance along with appreciated robustness due to lack of moveable parts.
Writing data to a solid-state memory device, such as a flash memory device, requires paying attention to specifics in the flash technology: NAND flash memory is organized in pages and blocks. Multiple pages form a block. While read and write operations can be applied to pages as the smallest entity of such operation, erase operations can only be applied to entire blocks. While in other storage technologies outdated data can simply be overwritten by up-to-date data, flash technology requires an erase operation before up-to-date data can be written to an erased block.
For the reason that flash technology erase operations can take much longer than read or write operations a writing technique called “write out of place” is applied in which new or updated data is written to some free page offered by a free page allocator instead of writing it to the same page where the outdated data resides. The page containing the outdated data is marked as invalid page.
The more data that is written over time, the less free pages can be offered and new blocks can be needed to be reclaimed for a free block queue. For example queue for providing free, i.e. erased blocks for writing new, or updated data to. New free blocks need to be reclaimed from blocks filled with valid and/or invalid data. The block reclaiming process—also known in literature as “garbage collection process”—first identifies blocks for cleaning based on a given policy. Then valid data still residing in these blocks is copied (relocated) to other blocks, and finally the blocks that are now free from valid data are erased and become available again for rewriting. Consequently, the block reclaiming process introduces additional read and write operations, the extent of which depends on the specific policy deployed as well as on system parameters.
In order to free up storage space that is occupied by invalid data there is a requirement to regularly perform block reclaiming. Since the block reclaiming process includes the relocation of valid pages from a reclaimed block to a free block and ensures the erasing of the reclaimed block, both of which tasks include copying and erasing operations representing write operations on the flash die, these operations compete with “regular” user read and write requests for access to the same storage resources, i.e., the flash dies. Scheduling is critical for the two classes of requests for accessing the dies that includes user perceived performance and proper execution of the block reclaiming process.
“A Semi-Preemptive Garbage Collector for Solid State Drives”, by Junghee Lee et al. in Performance Analysis of Systems and Software (ISPASS), 2011 IEEE International Symposium, 10-12 Apr. 2011 describes a semi-preemptive garbage collection that can preempt on-going garbage collection processing and service pending I/O requests in the queue. Flash performance is enhanced by pipelining internal garbage collection operations and merges them with pending I/O requests when possible.